package 图.有向图;

import 抽象数据类型.Digraph;
import 抽象数据类型.Queue;

import java.util.Stack;

/**
 * @description:
 * @author: ywk
 * @date: 2021-08-03
 */
public class 基于深度优先搜索的顶点排序 {
    public static class DepthFirstOrder {
        public boolean[] marked;
        private Queue<Integer> pre;
        private Queue<Integer> post;
        private Stack<Integer> reversePost;

        public DepthFirstOrder(Digraph g) {
            pre = new Queue<>();
            post = new Queue<>();
            reversePost = new Stack<>();
            marked = new boolean[g.V()];
            for (int v = 0; v < g.V(); v++) {
                if (!marked[v]) {
                    dfs(g, v);
                }
            }
        }

        private void dfs(Digraph g, int v) {
            pre.enqueue(v);
            marked[v] = true;
            for (Integer w : g.adj(v)) {
                if (!marked[w]) {
                    dfs(g, w);
                }
            }
            post.enqueue(v);
            reversePost.push(v);
        }

        public Iterable<Integer> pre() {
            return pre;
        }

        public Iterable<Integer> post() {
            return post;
        }

        public Iterable<Integer> reversePost() {
            return reversePost;
        }
    }

}
